package willis.sword.offer.algorithm.array;

/**
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素
 * 。例如数组{3,4,5,1,2}  {5,1,2,3,4}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
 */
public class RevolveArrayMin {


    public static int getMin(int[] array) {
        int x = 0;
        int y = array.length - 1;

        while (x < y) {
            int mid = x + ((y - x) >> 1);
            if (array[y] > array[x]) {
                return array[x];
            }
            //如果n 大于n+1 则n+1为最小的数 {3,4,|5(mid),1(mid+1)|,2}
            if (array[mid] > array[mid + 1]) {
                return array[mid + 1];
            }
            //如果n-1大于n的数 则输出n的数  {4,|5(mid-1),1(mid)|,2,3}
            if (array[mid-1] > array[mid]) {
                return array[mid];
            }
            if (array[0] > array[mid]) {
                //最小数在前半部分
                y = mid + 1;
            } else {
                //最小数在后半部分
                x = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
//        int[] arr={3,4,5,1,2};
//        int[] arr={5,1,2,3,4};
        int[] arr={1,2,3,4,5};
        System.out.println(getMin(arr));
    }


}
